iT邦幫忙

2024 iThome 鐵人賽

DAY 10
0

題目

2807. Insert Greatest Common Divisors in Linked List
難度: 中等偏易

題意

給定一串聯鏈結head,在相鄰的兩個節點中,插入新的節點,值為兩個節點值的最大公因數。

方向

遍歷head,若目前節點擁有下一個節點,則創建一個新節點,填入最大公因數,新節點的下一個指標指向目前節點的下一個節點,目前節點的下一個指標指向新節點
(簡單到不知道要擠什麼內容出來)

GCD特性:
https://hackmd.io/@sysprog/gcd-impl

實作

class Solution {
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode* curr = head;
        while(curr)
        {
            if(curr->next)
            {
                ListNode* insert = new ListNode(gcd(curr->val, curr->next->val), curr->next);
                curr->next = insert;
                curr = curr->next;
            }
            curr = curr->next;
        }
        return head;
    }
};

分析

head長度為N
時間複雜度: O(N),遍歷head長度為N
空間複雜度: O(N),建立N - 1個新節點

結果

Time Submitted Status Runtime Memory Language
09/10/2024 13:23 Accepted 35 ms 35.6 MB cpp

Accepted
582/582 cases passed (35 ms)
Your runtime beats 79.23 % of cpp submissions
Your memory usage beats 49.64 % of cpp submissions (35.6 MB)


上一篇
[9/9] 螺旋下殺
下一篇
[9/11] 數幾個不一樣
系列文
菜就多練,不會就多刷31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言